import random

def trace(func):
    """装饰器用于跟踪函数调用细节"""
    def wrapper(*args, **kwargs):
        result = func(*args, **kwargs)  # 调用原始函数
        print(f"{func.__name__}({', '.join(map(str, args))}): \n{result.pretty_print()}")  # 打印函数名、参数和结果
        print("--"*20)
        return result
    return wrapper


class IntSet:
    def include(self, x):
        raise NotImplementedError()

    def remove(self, x):
        raise NotImplementedError()

    def contains(self, x):
        raise NotImplementedError()

    def union(self, that):
        raise NotImplementedError()

    def intersection(self, that):
        raise NotImplementedError()

    def complement(self, that):
        raise NotImplementedError()

    def disjunctive_union(self, that):
        raise NotImplementedError()

    def pretty_print(self, depth=0):
        raise NotImplementedError()


class Empty(IntSet):
    def include(self, x):
        return NonEmpty(x, Empty(), Empty())

    def contains(self, x):
        return False

    def remove(self, x):
        return self

    @trace
    def union(self, that):
        return that

    def intersection(self, that):
        return self

    def complement(self, that):
        return that

    def disjunctive_union(self, that):
        return that

    def pretty_print(self, depth=0):
        return "  " * depth + "∅\n"

    def __str__(self):
        return "[*]"

class NonEmpty(IntSet):
    def __init__(self, elem, left=None, right=None):
        self.elem = elem
        self.left = left if left is not None else Empty()
        self.right = right if right is not None else Empty()

    def include(self, x):
        if x < self.elem:
            return NonEmpty(self.elem, self.left.include(x), self.right)
        elif x > self.elem:
            return NonEmpty(self.elem, self.left, self.right.include(x))
        else:
            return self

    def contains(self, x):
        if x < self.elem:
            return self.left.contains(x)
        elif x > self.elem:
            return self.right.contains(x)
        else:
            return True

    def remove(self, x):
        if x < self.elem:
            return NonEmpty(self.elem, self.left.remove(x), self.right)
        elif x > self.elem:
            return NonEmpty(self.elem, self.left, self.right.remove(x))
        else:
            return self.left.union(self.right)

    def find_min(self):
        if isinstance(self.left, Empty):
            return self.elem
        else:
            return self.left.find_min()

    def pretty_print(self, depth=0):
        result = ""
        if not isinstance(self.right, Empty):
            result += self.right.pretty_print(depth + 1)
        result += "  " * depth + str(self.elem) + "\n"
        if not isinstance(self.left, Empty):
            result += self.left.pretty_print(depth + 1)
        return result

    def __str__(self):
        return f"[{self.left} - [{self.elem}] - {self.right}]"


    @trace
    def union(self, that):
        return self.right.union(self.left.union(that)).include(self.elem)


# Testing the IntSet with both printing methods
tree1 = Empty()
tree1 = tree1.include(5)
tree1 = tree1.include(3)
tree1 = tree1.include(7)
tree1 = tree1.include(6)

print("tree1: \n")
print(tree1.pretty_print())

tree2 = Empty()
tree2 = tree2.include(2)
tree2 = tree2.include(8)
tree2 = tree2.include(3)
tree2 = tree2.include(9)

print("tree2: \n")
print(tree2.pretty_print())


print("union: \n")
union = tree1.union(tree2)
print(union.pretty_print())

print(union)

